package cn.cxq.learning.double_linked_list;

import org.junit.jupiter.api.Test;

/**
 * 剑指offer
 * 删除链表中重复的结点 相似的企业真题
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：693830
 * 本题知识点： 链表
 * 算法知识视频讲解
 * 题目描述
 * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
 * 示例1
 * 输入
 * 复制
 * {1,2,3,3,4,4,5}
 * 返回值
 * 复制
 * {1,2,5}
 */
public class DeleteDuplicate {

    @Test
    public void testDelete() {
        ListNode pHead = new ListNode(1);
        ListNode temp = pHead;
        temp.next = new ListNode(2);
        temp = temp.next;
        temp.next = new ListNode(3);
        temp = temp.next;
        temp.next = new ListNode(3);
        temp = temp.next;
        temp.next = new ListNode(4);
        temp = temp.next;
        temp.next = new ListNode(4);
        temp = temp.next;
        temp.next = new ListNode(5);
//        temp = temp.next;
//        temp.next = new ListNode(5);
//        temp = temp.next;
//        temp.next = new ListNode(7);
//        temp = temp.next;
//        temp.next = new ListNode(9);

        temp = pHead;
        ListNode listNode = deleteDuplication(temp);
        while (listNode != null) {

            System.out.println(deleteDuplication(listNode));
            listNode = listNode.next;
        }

    }

    //思路，使用一个头节点来方便写代码逻辑，pre指针用来存上一个找到的有效节点，cur用来存当前遍历到的节点
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode head = new ListNode(Integer.MIN_VALUE);
        head.next = pHead;

        ListNode cur = head.next;
        ListNode pre = head;

        while (cur != null) {
            if (cur.next != null && cur.val == cur.next.val) {
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                cur = cur.next;
            } else {
                pre.next = cur;
                pre = cur;
                cur = cur.next;
            }
        }

        //如果找不到了记得把最后一个节点指向空节点
        pre.next = null;

        pHead = head.next;
        return pHead;
    }
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}